1. Field of the Invention
This invention relates to integrated circuit design. More specifically, the invention relates to a method and apparatus for facilitating cell placement for an integrated circuit design.
2. Related Art
Cell placement is an important step in electronic design automation. During cell placement, cells are assigned physical locations within an IC (Integrated Circuit) design. A cell placement of an inferior quality is likely not only to affect the chip's performance, but it can also make it impossible to manufacture the chip by generating excessive wirelengths, which are beyond available routing resources. Consequently, a cell placement technique must perform the assignment while optimizing a number of objectives to ensure that an integrated circuit design meets its performance demands. A typical cell placement objective is to minimize the total wirelength (which is defined as the sum of the lengths of all the wires in the design) without violating the routing resource constraints.
Top-down partitioning-based cell placement is one of the popular approaches used for cell placement. This technique typically works by recursively dividing each partition into several sub-partitions, and at the same time dividing the contents of each partition into those sub-partitions. In addition, at each partitioning level, a pin-propagation step is performed to de-couple the dependencies of the various sub-partitions on the partitioning of the other sub-partitions as the partitioning goes deeper and deeper. An in-depth treatment of partitioning and partitioning-based placement techniques can be found in N. Sherwani, “Algorithms for VLSI Physical Design Automation,” 3rd Edition, Kluwer Academic Press, 1999.
Quadratic placement is one of the effective techniques for doing top-down partitioning-based placement. One of the basic ideas behind quadratic placement is that as interconnects become increasingly more important in defining the performance of the highly integrated circuits (due to scaling), long interconnects are likely to be more problematic, and on the timing critical paths. To alleviate this problem, and to penalize long wires, a quadratic formulation seeks to minimize the sum of the quadratic wire-lengths. In other words, in a quadratic formulation, one tries to find a place for all the movable objects such that the summation of the quadratic rectilinear distance of all the connected pairs of objects is minimized.
If there are no fixed boundary connections connecting the movable objects to the outside, the obvious solution to the quadratic formulation would be to place all the movable objects on top of one another, which is obviously not a feasible solution. The external connections act as a factor to distribute the movable objects across the chip.
Unfortunately, the solution from the quadratic solver can be infeasible because it does not meet the capacity constraints in various sections of the chip. Typically, the concentration of objects in some areas of the chip is extremely high, while the concentration of objects in other areas is extremely low.
Prior art techniques to remedy this problem have a number of drawbacks. These techniques are typically not very efficient, and hence they can take an enormous amount of time to determine a feasible cell placement. Additionally, prior art techniques are also very complicated, and hence are very difficult to implement, debug, and maintain.
Hence, what is needed is a method and an apparatus for determining a feasible cell placement which is computationally efficient and which is easy to implement, debug, and maintain.